/**
 * 分析：
            这道题说的是股票最多交易两次所得的最大利润，我们定义 dp[i][j]为在j天结束后最多交易i次所获得的最大利润。
            在这道题中我们知道 i 的可以取值只有 0 1 2

            1.如果我们在第 j 天的时候我们不交易，那么 
                dp[i][j] = dp[i][j-1];
            2.如果我们在第 j 天的时候我们卖出一支股票，这个时候我们假设卖出的这支股票是第 k 天买入的，那么当天结束后的利润就是：
                dp[i][j] = prices[j] - prices[k] + dp[i-1][k-1], k = [0,1,2,...j-1];
              prices [ j] - prices [k]表示的是在第k天买入一支股票，然后再第j天把它给卖掉所获 得的利润，其中k的范围是0…j -1。
              买一次卖一次算一次完整的交易，dp[i -1][k-1]表 示的是在前k-1天最多进行i -1次交易所获得的的最大利润。
            3.所以第j天我们可以选择卖出一支股票也可以选择不进行任何操作，取最大值即可，所 以递推公式如下
                dp[i][j] = Math.max(dp[i][j-1], prices[j] - prices[k] + dp[i - 1][k - 1]);
 * 
 * 
 * */
// 实现：
function maxProfit(prices) {
    var dp = [];
    for (let i = 0; i < 3; i++) {
        dp[i] = [];
        for (let j = 0; j < prices.length; j++) {
            dp[i][j] = 0;
        }
    }
    console.log(dp);

    for (let i = 1; i < 3; i++) {
        for (let j = 1; j < prices.length; j++) {
            for (let k = j - 1; k >= 0; k--) {
                var max = 0;
                if (k === 0) {
                    max = Math.max(dp[i][j - 1], prices[j] - prices[k]);
                } else {
                    max = Math.max(
                        dp[i][j - 1],
                        prices[j] - prices[k] + dp[i - 1][k - 1]
                    );
                }
                dp[i][j] = Math.max(dp[i][j], max);
            }
        }
    }
    return dp[2][prices.length - 1];
}